import java.util.Arrays;

/**
 * Created by yanin on 2017/11/13.
 */

public class MergeSort {


    public static void main(String args[]){
        int arr[]=new int[]{Integer.MIN_VALUE,2,4,5,7,1,2,3,6};
        mergeSort(arr,1,arr.length-1);
    }

    public static void merge(int arr[], int p, int q, int r){
        int n1=q-p+1;
        int n2=r-q;
        int R[]=new int[n1+1];
        int L[]=new int[n2+1];
        for (int i = 1; i <=n1; i++) {
            R[i]=arr[p+i-1];
        }
        for (int j = 1; j <=n2; j++) {
            L[j]=arr[q+j];
        }
        // R[n1+1]=Integer.MAX_VALUE;
        // L[n2+1]=Integer.MAX_VALUE;
        int i=1,j=1;
        int k = p;
        for (; i<=n1&&j<=n2; k++) {
            if(R[i]<=L[j]){
                arr[k]=R[i];
                i++;
            }else{
                arr[k]=L[j];
                j++;
            }
        }
        while(i<=n1){
            arr[k++]=R[i++];
        }
        while(j<=n2){
            arr[k++]=L[j++];
        }
     System.out.println(Arrays.toString(arr));
    }


    public static void mergeSort(int arr[], int p, int r){
        if(p<r){
            int q=(p+r)/2;
            System.out.println(p+"  "+ q+ "   "+r);
            mergeSort(arr,p,q);
            mergeSort(arr,q+1,r);
            merge(arr,p,q,r);
        }
    }

}
